/*
Given a set of non overlapping intervals
Example 1 :(1,4) (6,10) (14, 19) and another interval (13, 17) merge them as (1,4) (6,10) (13,19)

Example 2: (1,5) (6, 15) (20, 21) (23, 26) (27, 30) (35, 40)
New interval (14, 33)
Output should be 
(1,5) (6, 33) (35, 40)

This is because the new interval overlaps with (6, 15) (20, 21) (23, 26) (27, 30)
*/

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

typedef pair<int, int> PII;

vector<PII>  mergeInterval(vector<PII> &intervals, PII &newInterval)
{
    vector<PII> ans;
    bool mergeFinished = false;

    for (int i = 0; i < intervals.size(); i++) {
        if ((intervals[i].first > newInterval.first && intervals[i].first < newInterval.second)||
           (intervals[i].second > newInterval.first && intervals[i].second < newInterval.second)) {
            newInterval.first = min(intervals[i].first, newInterval.first);
            newInterval.second = max(intervals[i].second, newInterval.second);
            continue;
        }
        if (intervals[i].first > newInterval.second) {
            ans.push_back(make_pair(newInterval.first, newInterval.second));
            mergeFinished = true;
        }
        ans.push_back(intervals[i]);
    }
    if (!mergeFinished) ans.push_back(newInterval);
    return ans;
}

int main(int argc, char **argv)
{
    vector<PII> intervals;
    intervals.push_back(make_pair(1, 5));
   /* intervals.push_back(make_pair(6,15));
    intervals.push_back(make_pair(20, 21));
    intervals.push_back(make_pair(23, 26));
    intervals.push_back(make_pair(27, 30));
    intervals.push_back(make_pair(35, 40)); */
    PII newInterval(14, 33);
    vector<PII> ans = mergeInterval(intervals, newInterval);
    for (int i = 0; i < ans.size(); i++) 
	cout << ans[i].first << " " << ans[i].second << endl;
}
